package 单周赛.history;

import java.util.HashSet;
import java.util.Set;

/**
 *
 */
public class 第348场单周赛 {

    public static void main(String[] args) {

    }

    /**
     * 相同的字符不相邻也能删除
     */
    public int minimizedStringLength(String s) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            set.add(c);
        }
        return set.size();
    }

    /**
     * 需要注意 1 置换到索引 0 位置的时候，n 的位置可能变化
     */
    public int semiOrderedPermutation(int[] nums) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                cnt += i;
                while (i > 0) {
                    int t = nums[i - 1];
                    nums[i - 1] = nums[i];
                    nums[i] = t;
                    i--;
                }
                break;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == nums.length) {
                cnt += nums.length - i - 1;
                break;
            }
        }

        return cnt;
    }

    /**
     * 逆向思维+哈希表
     * 实际上表格里的某个值，会被最后一个查询覆盖，逆序遍历
     * 只需要取之后一次某行或者某列的变化，当需要修改的是行
     * 时，实际上之前遍历过的列会修改此行部分列，需要去除掉
     * 这部分的和，当需要修改的是列时，之前遍历过的行会修改
     * 此列部分的行，需要去除掉这部分的和
     * 注意：使用哈希表而不用数组记录是为了快速计算出已经访问过行数量或列数量
     */
    public long matrixSumQueries(int n, int[][] queries) {
        long ans = 0;
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        for (int i = queries.length - 1; i >= 0; i--) {
            if (rowSet.size() == n && colSet.size() == n) break;
            int type = queries[i][0], index = queries[i][1], val = queries[i][2];
            if (type == 0) {
                if (rowSet.contains(index)) {
                    continue;
                }
                // 除去访问过的列
                ans += val * (n - colSet.size());
                rowSet.add(index);
            }
            if (type == 1) {
                if (colSet.contains(index)) {
                    continue;
                }
                // 除去访问过的行
                ans += val * (n - rowSet.size());
                colSet.add(index);
            }
        }
        return ans;
    }

}
